{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Closest Nodes Queries in a Binary Search Tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #depth-first-search #array #binary-search #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #深度优先搜索 #数组 #二分查找 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: closestNodes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #二叉搜索树最近节点查询"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个 <strong>二叉搜索树</strong> 的根节点 <code>root</code> ，和一个由正整数组成、长度为 <code>n</code> 的数组 <code>queries</code> 。</p>\n",
    "\n",
    "<p>请你找出一个长度为 <code>n</code> 的 <strong>二维</strong> 答案数组 <code>answer</code> ，其中 <code>answer[i] = [min<sub>i</sub>, max<sub>i</sub>]</code> ：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>min<sub>i</sub></code> 是树中小于等于&nbsp;<code>queries[i]</code> 的 <strong>最大值</strong> 。如果不存在这样的值，则使用 <code>-1</code> 代替。</li>\n",
    "\t<li><code>max<sub>i</sub></code> 是树中大于等于&nbsp;<code>queries[i]</code> 的 <strong>最小值</strong> 。如果不存在这样的值，则使用 <code>-1</code> 代替。</li>\n",
    "</ul>\n",
    "\n",
    "<p>返回数组 <code>answer</code> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1 ：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2022/09/28/bstreeedrawioo.png\" style=\"width: 261px; height: 281px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [6,2,13,1,4,9,15,null,null,null,null,null,null,14], queries = [2,5,16]\n",
    "<strong>输出：</strong>[[2,2],[4,6],[15,-1]]\n",
    "<strong>解释：</strong>按下面的描述找出并返回查询的答案：\n",
    "- 树中小于等于 2 的最大值是 2 ，且大于等于 2 的最小值也是 2 。所以第一个查询的答案是 [2,2] 。\n",
    "- 树中小于等于 5 的最大值是 4 ，且大于等于 5 的最小值是 6 。所以第二个查询的答案是 [4,6] 。\n",
    "- 树中小于等于 16 的最大值是 15 ，且大于等于 16 的最小值不存在。所以第三个查询的答案是 [15,-1] 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2 ：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2022/09/28/bstttreee.png\" style=\"width: 101px; height: 121px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [4,null,9], queries = [3]\n",
    "<strong>输出：</strong>[[-1,4]]\n",
    "<strong>解释：</strong>树中不存在小于等于 3 的最大值，且大于等于 3 的最小值是 4 。所以查询的答案是 [-1,4] 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>树中节点的数目在范围 <code>[2, 10<sup>5</sup>]</code> 内</li>\n",
    "\t<li><code>1 &lt;= Node.val &lt;= 10<sup>6</sup></code></li>\n",
    "\t<li><code>n == queries.length</code></li>\n",
    "\t<li><code>1 &lt;= n &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= queries[i] &lt;= 10<sup>6</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [closest-nodes-queries-in-a-binary-search-tree](https://leetcode.cn/problems/closest-nodes-queries-in-a-binary-search-tree/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [closest-nodes-queries-in-a-binary-search-tree](https://leetcode.cn/problems/closest-nodes-queries-in-a-binary-search-tree/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[6,2,13,1,4,9,15,null,null,null,null,null,null,14]\\n[2,5,16]', '[4,null,9]\\n[3]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def closestNodes(self, root: Optional[TreeNode], queries: List[int]) -> List[List[int]]:\n",
    "        arr = []\n",
    "        queue = [root]\n",
    "        while len(queue)>0:\n",
    "            cur = queue.pop(0)\n",
    "            if cur is not None:\n",
    "                arr.append(cur.val)\n",
    "                queue += [cur.left, cur.right]\n",
    "        arr.sort()\n",
    "\n",
    "        ans_arr = []\n",
    "        for v in queries:\n",
    "            if v > arr[-1]:\n",
    "                ans_arr.append([arr[-1],-1])\n",
    "            elif v< arr[0]:\n",
    "                ans_arr.append([-1,arr[0]])\n",
    "            else:\n",
    "                i = bisect.bisect(arr,v)\n",
    "                if arr[i-1] == v:\n",
    "                    ans_arr.append([v,v])\n",
    "                else:\n",
    "                    ans_arr.append([arr[i-1],arr[i]])\n",
    "\n",
    "        return ans_arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def closestNodes(self, root: Optional[TreeNode], queries: List[int]) -> List[List[int]]:\n",
    "        res = []\n",
    "        record = []\n",
    "        stack = []\n",
    "        p = root\n",
    "        while p or stack:\n",
    "            if p:\n",
    "                stack.append(p)\n",
    "                p = p.left\n",
    "            else:\n",
    "                p = stack[-1]\n",
    "                record.append(p.val)\n",
    "                stack.pop()\n",
    "                p = p.right\n",
    "\n",
    "        for query in queries:\n",
    "            left,right = 0, len(record)-1\n",
    "            cur = [-1, -1]\n",
    "            while left<=right:\n",
    "                mid = (right-left)//2+left\n",
    "                if record[mid]==query:\n",
    "                    cur=[query, query]\n",
    "                    break\n",
    "                elif record[mid]<query:\n",
    "                    cur[0] = record[mid]\n",
    "                    left = mid+1\n",
    "                else:\n",
    "                    right = mid-1\n",
    "            else:\n",
    "                left,right=0,len(record)-1\n",
    "                while left<=right:\n",
    "                    mid = (right-left)//2+left\n",
    "                    if record[mid]==query:\n",
    "                        cur=[query,query]\n",
    "                        break\n",
    "                    elif record[mid]<query:\n",
    "                        left = mid+1\n",
    "                    else:\n",
    "                        cur[1]=record[mid]\n",
    "                        right = mid-1\n",
    "\n",
    "            res.append(cur)\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "class Solution:\n",
    "    def closestNodes(self, root: Optional[TreeNode], queries: List[int]) -> List[List[int]]:\n",
    "        t = []\n",
    "        q = deque([root])\n",
    "        while q:\n",
    "            node = q.popleft()\n",
    "            t.append(node.val)\n",
    "            if node.left: q.append(node.left)\n",
    "            if node.right: q.append(node.right)\n",
    "        t.sort()\n",
    "        ans = []\n",
    "        for que in queries:\n",
    "            idx = bisect_left(t, que)\n",
    "            if idx == len(t):\n",
    "                ans.append([t[-1], -1])\n",
    "            elif t[idx] == que:\n",
    "                ans.append([que, que])\n",
    "            elif idx == 0:\n",
    "                ans.append([-1, t[0]])\n",
    "            else:\n",
    "                ans.append([t[idx-1], t[idx]])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def closestNodes(self, root: Optional[TreeNode], queries: List[int]) -> List[List[int]]:\n",
    "        a = []\n",
    "        stack = []\n",
    "        while root or stack:\n",
    "            if root:\n",
    "                stack.append(root)\n",
    "                root = root.left\n",
    "            else:\n",
    "                root = stack.pop()\n",
    "                a.append(root.val)\n",
    "                root = root.right\n",
    "        n = len(a)\n",
    "        q = [(x, i) for i, x in enumerate(queries)]\n",
    "        q.sort()\n",
    "        res = [None] * len(q)\n",
    "        j = 0\n",
    "        for x, i in q:\n",
    "            while j < n and a[j] < x:\n",
    "                j += 1\n",
    "            if j < n:\n",
    "                if a[j] > x:\n",
    "                    if j > 0:\n",
    "                        res[i] = [a[j-1], a[j]]\n",
    "                    else:\n",
    "                        res[i] = [-1, a[0]]\n",
    "                else:\n",
    "                    res[i] = [x, x]\n",
    "            else:\n",
    "                res[i] = [a[n-1], -1]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def closestNodes(self, root: Optional[TreeNode], queries: List[int]) -> List[List[int]]:\n",
    "        cur=root \n",
    "        stack=[]\n",
    "        arr=[]\n",
    "        while cur or stack:\n",
    "            while cur:\n",
    "                stack.append(cur)\n",
    "                cur=cur.left \n",
    "            cur=stack.pop()\n",
    "            arr.append(cur.val)\n",
    "            cur=cur.right \n",
    "        ans=[]\n",
    "        n=len(arr)\n",
    "        for q in queries:\n",
    "            tmp=[]\n",
    "            idx=bisect.bisect(arr,q)\n",
    "            tmp.append(-1 if idx-1<0 else arr[idx-1])\n",
    "            idx=bisect.bisect_left(arr,q)\n",
    "            tmp.append(-1 if idx==n else arr[idx])\n",
    "            ans.append(tmp)\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def closestNodes(self, root: Optional[TreeNode], queries: List[int]) -> List[List[int]]:\n",
    "        ret=[]\n",
    "        s=set()\n",
    "        q=deque([root])\n",
    "        while q:\n",
    "            t=q.popleft()\n",
    "            s.add(t.val)\n",
    "            if t.right:\n",
    "                q.append(t.right)\n",
    "            if t.left:\n",
    "                q.append(t.left)\n",
    "        s=sorted(list(s))\n",
    "        for i in queries:\n",
    "            idx=bisect_left(s,i)\n",
    "            if idx==len(s):\n",
    "                ret.append([s[-1],-1])\n",
    "            elif s[idx]==i:\n",
    "                ret.append([i,i])\n",
    "            elif idx==0:\n",
    "                ret.append([-1,s[0]])\n",
    "            else:\n",
    "                ret.append([s[idx-1],s[idx]])\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def closestNodes(self, root: Optional[TreeNode], queries: List[int]) -> List[List[int]]:\n",
    "        arr = []\n",
    "        queue = [root]\n",
    "        while len(queue)>0:\n",
    "            cur = queue.pop(0)\n",
    "            if cur is not None:\n",
    "                arr.append(cur.val)\n",
    "                queue += [cur.left, cur.right]\n",
    "        arr.sort()\n",
    "        \n",
    "        def find(l,r,v):\n",
    "            if l==r:\n",
    "                if v == arr[l]:\n",
    "                    return [v,v]\n",
    "                else:\n",
    "                    return None\n",
    "            \n",
    "            if r == l+1:\n",
    "                if v == arr[l] or v == arr[r]:\n",
    "                    return [v,v]\n",
    "                else:\n",
    "                    return [arr[l],arr[r]]\n",
    "\n",
    "            m = (l+r) >> 1\n",
    "            if v>arr[m]:\n",
    "                ans = find(m,r,v)\n",
    "            elif v<arr[m]:\n",
    "                ans = find(l,m,v)\n",
    "            else:\n",
    "                ans = [v,v]\n",
    "\n",
    "            if ans is None:\n",
    "                ans = [arr[l],arr[r]]\n",
    "\n",
    "            return ans\n",
    "        \n",
    "        ans_arr = []\n",
    "        for v in queries:\n",
    "            if v > arr[-1]:\n",
    "                ans_arr.append([arr[-1],-1])\n",
    "            elif v< arr[0]:\n",
    "                ans_arr.append([-1,arr[0]])\n",
    "            else:\n",
    "                ans_arr.append(find(0,len(arr)-1,v))\n",
    "\n",
    "        return ans_arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def closestNodes(self, root: Optional[TreeNode], queries: List[int]) -> List[List[int]]:\n",
    "        tree = []\n",
    "        q = [root]\n",
    "        while q:\n",
    "            t = q.pop(0)\n",
    "            tree.append(t.val)\n",
    "            if t.left:\n",
    "                q.append(t.left)\n",
    "            if t.right:\n",
    "                q.append(t.right)\n",
    "        tree.sort()\n",
    "        # print(tree)\n",
    "        n = len(queries)\n",
    "        answer = [[-1, -1] for _ in range(n)]\n",
    "        q_idx = sorted(range(n), key=lambda x: queries[x])\n",
    "        # print(q_idx)\n",
    "        pre = nxt = 0\n",
    "        for i in q_idx:\n",
    "            while nxt < len(tree) and tree[nxt] < queries[i]:\n",
    "                pre = nxt\n",
    "                nxt += 1\n",
    "            if nxt == len(tree):\n",
    "                answer[i] = [tree[-1], -1]\n",
    "            elif tree[nxt] == queries[i]:\n",
    "                answer[i] = [tree[nxt], tree[nxt]]\n",
    "            elif tree[pre] <= queries[i]:\n",
    "                answer[i] = [tree[pre], tree[nxt]]\n",
    "            else:\n",
    "                answer[i][1] = tree[nxt]\n",
    "        return answer\n",
    "\n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def closestNodes(self, root: Optional[TreeNode], queries: List[int]) -> List[List[int]]:\n",
    "        l = list()\n",
    "        def dfs(node):\n",
    "            if node.left:\n",
    "                dfs(node.left)\n",
    "            l.append(node.val)\n",
    "            if node.right:\n",
    "                dfs(node.right)\n",
    "        dfs(root)\n",
    "        ans = list()\n",
    "        n = len(l)\n",
    "        for q in queries:\n",
    "            tmp = bisect_right(l, q)\n",
    "            min_val = l[tmp - 1] if tmp else -1\n",
    "            tmp = bisect_left(l, q)\n",
    "            max_val = l[tmp] if tmp != n else -1\n",
    "            ans.append([min_val, max_val])\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def closestNodes(self, root: Optional[TreeNode], queries: List[int]) -> List[List[int]]:\n",
    "        ans = []\n",
    "        nums = []\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return\n",
    "            dfs(node.left)\n",
    "            nums.append(node.val)\n",
    "            dfs(node.right)\n",
    "        dfs(root)\n",
    "        n = len(nums)\n",
    "        for q  in queries:\n",
    "            i = bisect_right(nums, q)\n",
    "            min = nums[i-1] if i else -1\n",
    "            j = bisect_left(nums, q)\n",
    "            max = nums[j] if j < n else -1\n",
    "            ans.append([min, max])\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestNodes(self, root: Optional[TreeNode], queries: List[int]) -> List[List[int]]:        \n",
    "        a = []\n",
    "        def dfs(o: Optional[TreeNode]) -> None:\n",
    "            if o is None: return\n",
    "            dfs(o.left)\n",
    "            a.append(o.val)\n",
    "            dfs(o.right)\n",
    "        dfs(root)\n",
    "\n",
    "        ans = []\n",
    "        for q in queries:\n",
    "            j = bisect_right(a, q)\n",
    "            min = a[j - 1] if j else -1\n",
    "            j = bisect_left(a, q)\n",
    "            max = a[j] if j < len(a) else -1\n",
    "            ans.append([min, max])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestNodes(self, root: Optional[TreeNode], queries: List[int]) -> List[List[int]]:\n",
    "        a = []\n",
    "        def dfs(o: Optional[TreeNode]) -> None:\n",
    "            if o is None: return\n",
    "            dfs(o.left)\n",
    "            a.append(o.val)\n",
    "            dfs(o.right)\n",
    "        dfs(root)\n",
    "\n",
    "        ans = []\n",
    "        for q in queries:\n",
    "            j = bisect_right(a, q)\n",
    "            min = a[j - 1] if j else -1\n",
    "            j = bisect_left(a, q)\n",
    "            max = a[j] if j < len(a) else -1\n",
    "            ans.append([min, max])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def closestNodes(self, root: Optional[TreeNode], queries: List[int]) -> List[List[int]]:\n",
    "        tree = []\n",
    "        def dfs(o:Optional[TreeNode]) -> None:\n",
    "            if o is None:\n",
    "                return \n",
    "            dfs(o.left)\n",
    "            tree.append(o.val)\n",
    "            dfs(o.right)\n",
    "        \n",
    "        dfs(root)\n",
    "\n",
    "        ans = []\n",
    "        for q in queries:\n",
    "            j = bisect_right(tree, q)\n",
    "            min = tree[j-1] if j else -1\n",
    "            j = bisect_left(tree, q)\n",
    "            max = tree[j] if j < len(tree) else -1\n",
    "            ans.append([min, max])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def closestNodes(self, root: Optional[TreeNode], queries: List[int]) -> List[List[int]]:\n",
    "        res = []\n",
    "        def dfs(node : Optional[TreeNode]):\n",
    "            if node is None:\n",
    "                return\n",
    "            dfs(node.left)\n",
    "            res.append(node.val)\n",
    "            dfs(node.right)\n",
    "        dfs(root)\n",
    "        ans = []\n",
    "        for q in queries:\n",
    "            i = bisect_right(res, q)\n",
    "            j = bisect_left(res, q)\n",
    "            min = res[i - 1] if i else -1\n",
    "            max = res[j] if j < len(res) else -1\n",
    "            ans.append([min, max])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def closestNodes(self, root: Optional[TreeNode], queries: List[int]) -> List[List[int]]:\n",
    "        tree = []\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return\n",
    "            dfs(root.left)\n",
    "            tree.append(root.val)\n",
    "            dfs(root.right)\n",
    "        def left_max(target, nums):\n",
    "            left = 0\n",
    "            right = len(nums)-1\n",
    "            ans = -1\n",
    "            while left <= right:\n",
    "                mid = (left+right)//2\n",
    "                if nums[mid] == target:\n",
    "                    return nums[mid]\n",
    "                elif nums[mid] >target:\n",
    "                    right = mid-1\n",
    "                else:\n",
    "                    left = mid+1\n",
    "                    ans = max(ans, nums[mid])\n",
    "            return ans\n",
    "        def right_min(target, nums):\n",
    "            left = 0\n",
    "            right = len(nums)-1\n",
    "            ans = inf\n",
    "            while left <= right:\n",
    "                mid = (left+right)//2\n",
    "                if nums[mid] == target:\n",
    "                    return nums[mid]\n",
    "                elif nums[mid] >target:\n",
    "                    right = mid-1\n",
    "                    ans = min(ans, nums[mid])\n",
    "                else:\n",
    "                    left = mid+1\n",
    "            if ans == inf:\n",
    "                return -1\n",
    "            else:               \n",
    "                return ans\n",
    "\n",
    "\n",
    "        dfs(root)\n",
    "        res = []\n",
    "        for i in queries:\n",
    "            l = left_max(i, tree)\n",
    "            r = right_min(i, tree)\n",
    "            res.append([l, r])\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "class Solution:\n",
    "    def closestNodes(self, root: Optional[TreeNode], queries: List[int]) -> List[List[int]]:\n",
    "        arr = []\n",
    "        def dfs(root):\n",
    "            if root:\n",
    "                dfs(root.left)\n",
    "                arr.append(root.val)\n",
    "                dfs(root.right)\n",
    "        dfs(root)\n",
    "        n = len(arr)\n",
    "        ans = []\n",
    "        for q in queries:\n",
    "            i = bisect_left(arr,q)\n",
    "            j = bisect_right(arr,q)\n",
    "            maxSize = arr[i] if i<n else -1\n",
    "            minSize = arr[j-1] if j else -1\n",
    "            ans.append([minSize,maxSize])\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def closestNodes(self, root: Optional[TreeNode], queries: List[int]) -> List[List[int]]:\n",
    "        def dfs_LNR(rt: TreeNode):\n",
    "            nonlocal nums\n",
    "            if rt:\n",
    "                dfs_LNR(rt.left)\n",
    "                nums.append(rt.val)\n",
    "                dfs_LNR(rt.right)\n",
    "        \n",
    "        nums = []\n",
    "        dfs_LNR(root)\n",
    "        \n",
    "        n = len(nums)\n",
    "        \n",
    "        res = []\n",
    "        for x in queries:\n",
    "            a, b = -1, -1\n",
    "            i = bisect.bisect_right(nums, x)\n",
    "            a = nums[i - 1] if 0 <= i - 1 else -1                    \n",
    "            i = bisect.bisect_left(nums, x)\n",
    "            b = nums[i] if i < n else -1\n",
    "            res.append([a, b])\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def closestNodes(self, root: Optional[TreeNode], queries: List[int]) -> List[List[int]]:\n",
    "        res = [] \n",
    "        def traverse(node):\n",
    "            if node:\n",
    "                traverse(node.left)\n",
    "                res.append(node.val)\n",
    "                traverse(node.right)\n",
    "        traverse(root)\n",
    "        answer = []\n",
    "        for i in queries:\n",
    "            max_num = i\n",
    "            min_num = i\n",
    "            # 二分查找 大于等于 queries[i] 的 最小值\n",
    "            left = 0\n",
    "            right = len(res) - 1\n",
    "            while left <= right:\n",
    "                mid = (left+right)//2\n",
    "                if res[mid] >= max_num:\n",
    "                    right = mid-1\n",
    "                else:\n",
    "                    left = mid+1\n",
    "            if left != len(res):\n",
    "                a2 = res[left]\n",
    "            else:\n",
    "                a2 = -1\n",
    "            left = 0\n",
    "            right = len(res)-1\n",
    "            while left <= right:\n",
    "                mid = (left + right)//2\n",
    "                if res[mid] <= min_num:\n",
    "                    left = mid + 1\n",
    "                else:\n",
    "                    right = mid - 1\n",
    "            if left != 0:\n",
    "                a1 = res[right]\n",
    "            else:\n",
    "                a1 = -1\n",
    "            answer.append([a1,a2])\n",
    "        return answer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def closestNodes(self, root: Optional[TreeNode], queries: List[int]) -> List[List[int]]:\n",
    "        res = [] \n",
    "        def traverse(node):\n",
    "            if node:\n",
    "                traverse(node.left)\n",
    "                res.append(node.val)\n",
    "                traverse(node.right)\n",
    "        traverse(root)\n",
    "        answer = []\n",
    "        for i in queries:\n",
    "            max_num = i\n",
    "            min_num = i\n",
    "            # 二分查找 大于等于 queries[i] 的 最小值\n",
    "            left = 0\n",
    "            right = len(res) - 1\n",
    "            while left <= right:\n",
    "                mid = (left+right)//2\n",
    "                if res[mid] >= max_num:\n",
    "                    right = mid-1\n",
    "                else:\n",
    "                    left = mid+1\n",
    "            if left != len(res):\n",
    "                a2 = res[left]\n",
    "            else:\n",
    "                a2 = -1\n",
    "            left = 0\n",
    "            right = len(res)-1\n",
    "            while left <= right:\n",
    "                mid = (left + right)//2\n",
    "                if res[mid] <= min_num:\n",
    "                    left = mid + 1\n",
    "                else:\n",
    "                    right = mid - 1\n",
    "            if left != 0:\n",
    "                a1 = res[right]\n",
    "            else:\n",
    "                a1 = -1\n",
    "            answer.append([a1,a2])\n",
    "        return answer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def closestNodes(self, root: Optional[TreeNode], queries: List[int]) -> List[List[int]]:        \n",
    "        a = []\n",
    "        def dfs(o: Optional[TreeNode]) -> None:\n",
    "            if o is None: return\n",
    "            dfs(o.left)\n",
    "            a.append(o.val)\n",
    "            dfs(o.right)\n",
    "        dfs(root)\n",
    "\n",
    "        ans = []\n",
    "        for q in queries:\n",
    "            j = bisect_right(a, q)\n",
    "            min = a[j - 1] if j else -1\n",
    "            j = bisect_left(a, q)\n",
    "            max = a[j] if j < len(a) else -1\n",
    "            ans.append([min, max])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestNodes(self, root: Optional[TreeNode], queries: List[int]) -> List[List[int]]:\n",
    "        a = []\n",
    "        def dfs(o: Optional[TreeNode]) -> None:\n",
    "            if o is None: return\n",
    "            dfs(o.left)\n",
    "            a.append(o.val)\n",
    "            dfs(o.right)\n",
    "        dfs(root)\n",
    "\n",
    "        ans = []\n",
    "        for q in queries:\n",
    "            j = bisect_right(a, q)\n",
    "            min = a[j - 1] if j else -1\n",
    "            j = bisect_left(a, q)\n",
    "            max = a[j] if j < len(a) else -1\n",
    "            ans.append([min, max])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def closestNodes(self, root: Optional[TreeNode], queries: List[int]) -> List[List[int]]:\n",
    "        res = []\n",
    "        def dfs(node):\n",
    "            if node:\n",
    "                res.append(node.val)\n",
    "                dfs(node.left)\n",
    "                dfs(node.right)\n",
    "        dfs(root)\n",
    "        res.sort()\n",
    "        ans = []\n",
    "        for q in queries:\n",
    "            i = bisect_left(res, q)\n",
    "            right = res[i] if i < len(res) else -1\n",
    "            left = -1\n",
    "            if i == 0:\n",
    "                if res[i] == q:\n",
    "                    left = res[i]\n",
    "            elif i < len(res):\n",
    "                left = res[i] if res[i] == q else res[i - 1]\n",
    "            else:\n",
    "                left = res[i - 1]\n",
    "            ans.append([left, right])\n",
    "        return ans\n",
    "            \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def closestNodes(self, root: Optional[TreeNode], queries: List[int]) -> List[List[int]]:\n",
    "\n",
    "        a = []\n",
    "\n",
    "        def dfs(o: Optional[TreeNode]) -> None:\n",
    "\n",
    "            if o is None: return\n",
    "\n",
    "            dfs(o.left)\n",
    "\n",
    "            a.append(o.val)\n",
    "\n",
    "            dfs(o.right)\n",
    "\n",
    "        dfs(root)\n",
    "\n",
    "\n",
    "\n",
    "        ans = []\n",
    "\n",
    "        for q in queries:\n",
    "\n",
    "            j = bisect_right(a, q)\n",
    "\n",
    "            min = a[j - 1] if j else -1\n",
    "\n",
    "            j = bisect_left(a, q)\n",
    "\n",
    "            max = a[j] if j < len(a) else -1\n",
    "\n",
    "            ans.append([min, max])\n",
    "\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestNodes(self, root: Optional[TreeNode], queries: List[int]) -> List[List[int]]:\n",
    "        a = []\n",
    "        def dfs(o: Optional[TreeNode]) -> None:\n",
    "            if o is None: return\n",
    "            dfs(o.left)\n",
    "            a.append(o.val)\n",
    "            dfs(o.right)\n",
    "        dfs(root)\n",
    "\n",
    "        ans = []\n",
    "        for q in queries:\n",
    "            j = bisect_right(a, q)\n",
    "            min = a[j - 1] if j else -1\n",
    "            j = bisect_left(a, q)\n",
    "            max = a[j] if j < len(a) else -1\n",
    "            ans.append([min, max])\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestNodes(self, root: Optional[TreeNode], queries: List[int]) -> List[List[int]]:\n",
    "        a = []\n",
    "        def dfs(o: Optional[TreeNode]) -> None:\n",
    "            if o is None: return\n",
    "            dfs(o.left)\n",
    "            a.append(o.val)\n",
    "            dfs(o.right)\n",
    "        dfs(root)\n",
    "\n",
    "        ans = []\n",
    "        for q in queries:\n",
    "            j = bisect_right(a, q)\n",
    "            min = a[j - 1] if j else -1\n",
    "            j = bisect_left(a, q)\n",
    "            max = a[j] if j < len(a) else -1\n",
    "            ans.append([min, max])\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def closestNodes(self, root: Optional[TreeNode], queries: List[int]) -> List[List[int]]:\n",
    "        # 中序遍历 + 二分查找\n",
    "        a = []\n",
    "        def dfs(node):\n",
    "            if node is None:\n",
    "                return\n",
    "            dfs(node.left)\n",
    "            a.append(node.val)\n",
    "            dfs(node.right)\n",
    "        dfs(root)\n",
    "\n",
    "        ans = []\n",
    "        for q in queries:\n",
    "            i = bisect_right(a, q)\n",
    "            min = a[i - 1] if i else -1\n",
    "            i = bisect_left(a, q)\n",
    "            max = a[i] if i < len(a) else -1\n",
    "            ans.append([min, max])\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def closestNodes(self, root: Optional[TreeNode], queries: List[int]) -> List[List[int]]:\n",
    "        v = []\n",
    "        def dfs(cur):\n",
    "            if cur == None:\n",
    "                return\n",
    "            dfs(cur.left)\n",
    "            v.append(cur.val)\n",
    "            dfs(cur.right)\n",
    "        dfs(root)\n",
    "        n = len(v)\n",
    "        ans = [[-1, -1] for _ in range(len(queries))]\n",
    "        for i, x in enumerate(queries):\n",
    "            a = bisect_right(v, x)\n",
    "            b = bisect_left(v, x)\n",
    "            if a - 1 >= 0:\n",
    "                ans[i][0] = v[a - 1]\n",
    "            if b < n:\n",
    "                ans[i][1] = v[b]\n",
    "        # print(v)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def closestNodes(self, root: Optional[TreeNode], queries: List[int]) -> List[List[int]]:\n",
    "        a=[]\n",
    "        def dfs(o):\n",
    "            if not o:\n",
    "                return\n",
    "            dfs(o.left)\n",
    "            a.append(o.val)\n",
    "            dfs(o.right)\n",
    "        dfs(root)\n",
    "\n",
    "        ans=[]\n",
    "        for q in queries:\n",
    "            j=bisect_right(a,q)\n",
    "            min_ = a[j-1] if j else -1\n",
    "            j=bisect_left(a,q)\n",
    "            max_ = a[j] if j<len(a) else -1\n",
    "            ans.append([min_,max_])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestNodes(self, root: Optional[TreeNode], queries: List[int]) -> List[List[int]]:\n",
    "        a = []\n",
    "        def dfs(o: Optional[TreeNode]) -> None:\n",
    "            if o is None: return\n",
    "            dfs(o.left)\n",
    "            a.append(o.val)\n",
    "            dfs(o.right)\n",
    "        dfs(root)\n",
    "\n",
    "        ans = []\n",
    "        for q in queries:\n",
    "            j = bisect_right(a, q)\n",
    "            min = a[j - 1] if j else -1\n",
    "            j = bisect_left(a, q)\n",
    "            max = a[j] if j < len(a) else -1\n",
    "            ans.append([min, max])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def closestNodes(self, root: Optional[TreeNode], queries: List[int]) -> List[List[int]]:\n",
    "        a = []\n",
    "        def dfs(o: Optional[TreeNode]) -> None:\n",
    "            if o is None: return\n",
    "            dfs(o.left)\n",
    "            a.append(o.val)\n",
    "            dfs(o.right)\n",
    "        dfs(root)\n",
    "\n",
    "        ans = []\n",
    "        for q in queries:\n",
    "            j = bisect_right(a, q)\n",
    "            min = a[j - 1] if j else -1\n",
    "            j = bisect_left(a, q)\n",
    "            max = a[j] if j < len(a) else -1\n",
    "            ans.append([min, max])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def closestNodes(self, root: Optional[TreeNode], queries: List[int]) -> List[List[int]]:\n",
    "        vals = []\n",
    "\n",
    "        # 中序遍历\n",
    "        def inorder(root):\n",
    "            if not root:\n",
    "                return\n",
    "            inorder(root.left)\n",
    "            vals.append(root.val)\n",
    "            inorder(root.right)\n",
    "\n",
    "        inorder(root)\n",
    "\n",
    "        ans = []\n",
    "        for q in queries:\n",
    "            cur = [-1, -1]\n",
    "            # upper_bound等价\n",
    "            lit = bisect.bisect_right(vals, q)\n",
    "            if lit != 0:\n",
    "                cur[0] = vals[lit - 1]\n",
    "            # lower_bound等价\n",
    "            rit = bisect.bisect_left(vals, q)\n",
    "            if rit != len(vals):\n",
    "                cur[1] = vals[rit]\n",
    "            ans.append(cur)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def closestNodes(self, root: Optional[TreeNode], queries: List[int]) -> List[List[int]]:\n",
    "        tree = []\n",
    "        # 使用队列得到值列表\n",
    "        # q = [root]\n",
    "        # while q:\n",
    "        #     t = q.pop(0)\n",
    "        #     tree.append(t.val)\n",
    "        #     if t.left:\n",
    "        #         q.append(t.left)\n",
    "        #     if t.right:\n",
    "        #         q.append(t.right)\n",
    "        def dfs(nt):\n",
    "            if nt:\n",
    "                tree.append(nt.val)\n",
    "                dfs(nt.left)\n",
    "                dfs(nt.right)\n",
    "\n",
    "        dfs(root)\n",
    "        tree.sort()\n",
    "        print(tree)\n",
    "        n = len(queries)\n",
    "        answer = [[-1, -1] for _ in range(n)]\n",
    "        q_idx = sorted(range(n), key=lambda x: queries[x])\n",
    "        # print(q_idx)\n",
    "        pre = nxt = 0\n",
    "        for i in q_idx:\n",
    "            while nxt < len(tree) and tree[nxt] < queries[i]:\n",
    "                pre = nxt\n",
    "                nxt += 1\n",
    "            if nxt == len(tree):\n",
    "                answer[i] = [tree[-1], -1]\n",
    "            elif tree[nxt] == queries[i]:\n",
    "                answer[i] = [tree[nxt], tree[nxt]]\n",
    "            elif tree[pre] <= queries[i]:\n",
    "                answer[i] = [tree[pre], tree[nxt]]\n",
    "            else:\n",
    "                answer[i][1] = tree[nxt]\n",
    "        return answer\n",
    "\n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def closestNodes(self, root: Optional[TreeNode], queries: List[int]) -> List[List[int]]:\n",
    "        nums = []\n",
    "        def dfs(node: Optional[TreeNode]) -> None:\n",
    "            if node is None: return\n",
    "            dfs(node.left)\n",
    "            nums.append(node.val)\n",
    "            dfs(node.right)\n",
    "        dfs(root)\n",
    "\n",
    "        ans = []\n",
    "        for q in queries:\n",
    "            j = bisect_right(nums, q)\n",
    "            a = nums[j - 1] if j else -1\n",
    "            j = bisect_left(nums, q)\n",
    "            b = nums[j] if j < len(nums) else -1\n",
    "            ans.append([a,b])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def closestNodes(self, root: Optional[TreeNode], queries: List[int]) -> List[List[int]]:\n",
    "       class TreeNode:\n",
    "          def __init__(self, val=0, left=None, right=None):\n",
    "             self.val = val\n",
    "             self.left = left\n",
    "             self.right = right\n",
    "       def dfs(root: Optional[TreeNode]) -> None:\n",
    "          if not root:\n",
    "             return\n",
    "          dfs(root.left)\n",
    "          arr.append(root.val)\n",
    "          dfs(root.right)\n",
    "       arr = []\n",
    "       dfs(root)\n",
    "       n = len(arr)\n",
    "       res = []\n",
    "       for q in queries:\n",
    "          x = bisect.bisect_right(arr, q)\n",
    "          min_val = arr[x - 1] if x else -1\n",
    "          y = bisect.bisect_left(arr, q)\n",
    "          max_val = arr[y] if y < n else -1\n",
    "          res.append([min_val, max_val])\n",
    "       return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def closestNodes(self, root: Optional[TreeNode], queries: List[int]) -> List[List[int]]:\n",
    "        ans = []\n",
    "        def dfs(node):\n",
    "            if node is None: return\n",
    "            dfs(node.left)\n",
    "            ans.append(node.val)\n",
    "            dfs(node.right)\n",
    "        dfs(root)\n",
    "\n",
    "        res = []\n",
    "        for query in queries:\n",
    "            i = bisect_right(ans, query)\n",
    "            min_ans = ans[i - 1] if i else -1\n",
    "            j = bisect_left(ans, query)\n",
    "            max_ans = ans[j] if j < len(ans) else -1\n",
    "            res.append([min_ans, max_ans])\n",
    "\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def closestNodes(self, root: Optional[TreeNode], q: List[int]) -> List[List[int]]:\n",
    "        v=[]\n",
    "        def dfs(r):\n",
    "            if not r:\n",
    "                return\n",
    "            v.append(r.val)\n",
    "            dfs(r.left)\n",
    "            dfs(r.right)\n",
    "        dfs(root)\n",
    "        v.sort()\n",
    "        ans=[]\n",
    "        for i in q:\n",
    "            j,k=bisect_left(v,i),bisect_right(v,i)\n",
    "            v1,v2=-1,-1\n",
    "            if k>0:\n",
    "                v1=v[k-1]\n",
    "            if j<len(v):\n",
    "                v2=v[j]\n",
    "            ans.append([v1,v2])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def closestNodes(self, root: Optional[TreeNode], queries: List[int]) -> List[List[int]]:\n",
    "        n = len(queries)\n",
    "        arr, result = [], [[-1, -1] for _ in range(n)]\n",
    "        dfs = lambda n: n and (dfs(n.left) or arr.append(n.val) or dfs(n.right))\n",
    "        dfs(root)\n",
    "        q = sorted(range(n), key=queries.__getitem__)\n",
    "        prev, i = -1, 0\n",
    "        for x in arr:\n",
    "            while i < n and queries[q[i]] <= x:\n",
    "                if queries[q[i]] == x:\n",
    "                    prev = x\n",
    "                result[q[i]][:] = prev, x\n",
    "                i += 1\n",
    "            if i < n:\n",
    "                result[q[i]][0] = x\n",
    "                prev = x\n",
    "            else:\n",
    "                break\n",
    "        while i < n:\n",
    "            result[q[i]][0] = prev\n",
    "            i += 1\n",
    "        return result\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def closestNodes(self, root: Optional[TreeNode], queries: List[int]) -> List[List[int]]:\n",
    "        l = list()\n",
    "        def dfs(node):\n",
    "            if node.left:\n",
    "                dfs(node.left)\n",
    "            l.append(node.val)\n",
    "            if node.right:\n",
    "                dfs(node.right)\n",
    "        dfs(root)\n",
    "        ans = list()\n",
    "        l = [-1] + l + [inf]\n",
    "        n = len(l)\n",
    "        for q in queries:\n",
    "            tmp = bisect.bisect_left(l, q)\n",
    "            min_val = l[tmp] if l[tmp] == q else l[tmp - 1]\n",
    "            max_val = l[tmp] if tmp != n - 1 else -1\n",
    "            ans.append([min_val, max_val])\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def closestNodes(self, root: Optional[TreeNode], queries: List[int]) -> List[List[int]]:        \n",
    "        h = sorted(set(queries), reverse=True)\n",
    "        ans = {}\n",
    "\n",
    "        a, b = -1, -1\n",
    "        def dfs(o: Optional[TreeNode]) -> None:\n",
    "            nonlocal a, b\n",
    "            if o is None: return\n",
    "            dfs(o.left)\n",
    "            a, b = b, o.val\n",
    "            while h and h[-1] <= b:\n",
    "                x = h.pop()\n",
    "                ans[x] = a if x < b else b, b\n",
    "            dfs(o.right)\n",
    "        \n",
    "        dfs(root)\n",
    "        while h:\n",
    "            x = h.pop()\n",
    "            ans[x] = (b, -1)\n",
    "\n",
    "        return [ans[x] for x in queries]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def closestNodes(self, root: Optional[TreeNode], queries: List[int]) -> List[List[int]]:        \n",
    "        h = sorted(set(queries), reverse=True)\n",
    "        ans = {}\n",
    "\n",
    "        a, b = -1, -1\n",
    "        def dfs(o: Optional[TreeNode]) -> None:\n",
    "            nonlocal a, b\n",
    "            if o is None: return\n",
    "            dfs(o.left)\n",
    "            a, b = b, o.val\n",
    "            while h and h[-1] <= b:\n",
    "                x = h.pop()\n",
    "                ans[x] = a if x < b else b, b\n",
    "            dfs(o.right)\n",
    "        \n",
    "        dfs(root)\n",
    "        while h:\n",
    "            x = h.pop()\n",
    "            ans[x] = (b, -1)\n",
    "\n",
    "        return [ans[x] for x in queries]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def closestNodes(self, root: Optional[TreeNode], queries: List[int]) -> List[List[int]]:        \n",
    "        h = sorted(set(queries), reverse=True)\n",
    "        ans = {}\n",
    "\n",
    "        a, b = -1, -1\n",
    "        def dfs(o: Optional[TreeNode]) -> None:\n",
    "            nonlocal a, b\n",
    "            if o is None: return\n",
    "            dfs(o.left)\n",
    "            a, b = b, o.val\n",
    "            while h and h[-1] <= b:\n",
    "                x = h.pop()\n",
    "                ans[x] = a if x < b else b, b\n",
    "            dfs(o.right)\n",
    "        \n",
    "        dfs(root)\n",
    "        while h:\n",
    "            x = h.pop()\n",
    "            ans[x] = (b, -1)\n",
    "\n",
    "        return [ans[x] for x in queries]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def closestNodes(self, root: Optional[TreeNode], queries: List[int]) -> List[List[int]]:\n",
    "        n = len(queries)\n",
    "        res = [[-1, -1] for _ in range(n)]\n",
    "        sorted_queries = sorted([q, index] for index, q in enumerate(queries))\n",
    "        num_list = []\n",
    "\n",
    "        def dfs(now):\n",
    "            if now.left:\n",
    "                dfs(now.left)\n",
    "            num_list.append(now.val)\n",
    "            if now.right:\n",
    "                dfs(now.right)\n",
    "\n",
    "        dfs(root)\n",
    "\n",
    "        pre = -1\n",
    "        p = 0\n",
    "\n",
    "        for num in num_list:\n",
    "            while p < n and sorted_queries[p][0] < num:\n",
    "                res[sorted_queries[p][1]] = [pre, num]\n",
    "                p += 1\n",
    "            while p < n and sorted_queries[p][0] == num:\n",
    "                res[sorted_queries[p][1]] = [num, num]\n",
    "                p += 1\n",
    "            pre = num\n",
    "        \n",
    "        while p < n:\n",
    "            res[sorted_queries[p][1]] = [pre, -1]\n",
    "            p += 1\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def closestNodes(self, root: Optional[TreeNode], queries: List[int]) -> List[List[int]]:        \n",
    "        h = list(set(queries))\n",
    "        heapify(h)\n",
    "        ans = {}\n",
    "\n",
    "        a, b = -1, -1\n",
    "        def dfs(o: Optional[TreeNode]) -> None:\n",
    "            nonlocal a, b\n",
    "            if o is None: return\n",
    "            dfs(o.left)\n",
    "            a, b = b, o.val\n",
    "            while h and h[0] <= b:\n",
    "                x = heappop(h)\n",
    "                ans[x] = a if x < b else b, b\n",
    "            dfs(o.right)\n",
    "        \n",
    "        dfs(root)\n",
    "        while h:\n",
    "            x = heappop(h)\n",
    "            ans[x] = (b, -1)\n",
    "\n",
    "        return [ans[x] for x in queries]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def closestNodes(self, root: Optional[TreeNode], queries: List[int]) -> List[List[int]]:        \n",
    "        h = list(set(queries))\n",
    "        heapify(h)\n",
    "        ans = {}\n",
    "\n",
    "        a, b = -1, -1\n",
    "        def dfs(o: Optional[TreeNode]) -> None:\n",
    "            nonlocal a, b\n",
    "            if o is None: return\n",
    "            dfs(o.left)\n",
    "            a, b = b, o.val\n",
    "            while h and h[0] <= b:\n",
    "                x = heappop(h)\n",
    "                ans[x] = (a if x < b else b, b)\n",
    "            dfs(o.right)\n",
    "        \n",
    "        dfs(root)\n",
    "        while h:\n",
    "            x = heappop(h)\n",
    "            ans[x] = (b, -1)\n",
    "\n",
    "        return [ans[x] for x in queries]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def closestNodes(self, root: Optional[TreeNode], queries: List[int]) -> List[List[int]]:        \n",
    "        h = list(set(queries))\n",
    "        heapify(h)\n",
    "        ans = {}\n",
    "\n",
    "        a, b = -1, -1\n",
    "        def dfs(o: Optional[TreeNode]) -> None:\n",
    "            nonlocal a, b\n",
    "            if o is None: return\n",
    "            dfs(o.left)\n",
    "            a, b = b, o.val\n",
    "            while h and h[0] <= b:\n",
    "                x = heappop(h)\n",
    "                ans[x] = b if x == b else a, b\n",
    "            dfs(o.right)\n",
    "        \n",
    "        dfs(root)\n",
    "        while h:\n",
    "            x = heappop(h)\n",
    "            ans[x] = (b, -1)\n",
    "\n",
    "        return [ans[x] for x in queries]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def closestNodes(self, root: Optional[TreeNode], queries: List[int]) -> List[List[int]]:        \n",
    "        l = []\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return\n",
    "            dfs(node.left)\n",
    "            l.append(node.val)\n",
    "            dfs(node.right)\n",
    "        dfs(root)\n",
    "\n",
    "        def query(n):\n",
    "            if n > l[-1]:\n",
    "                return [l[-1], -1]\n",
    "            if n < l[0]:\n",
    "                return [-1, l[0]]\n",
    "            i = bisect_left(l, n)\n",
    "            return [n, n] if l[i] == n else [l[i - 1], l[i]]\n",
    "\n",
    "        return [*map(query, queries)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def closestNodes(self, root: Optional[TreeNode], queries: List[int]) -> List[List[int]]:\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return\n",
    "\n",
    "            dfs(root.left)\n",
    "            ls.append(root.val)\n",
    "            dfs(root.right)\n",
    "\n",
    "        ls = []\n",
    "        dfs(root)\n",
    "\n",
    "        ans = []\n",
    "\n",
    "        for q in queries:\n",
    "            idx = bisect.bisect_left(ls, q)\n",
    "            if idx == len(ls):\n",
    "                max_ = -1\n",
    "            else:\n",
    "                max_ = ls[idx]\n",
    "            \n",
    "            if idx == len(ls):\n",
    "                min_ = ls[-1]\n",
    "            else:\n",
    "                if ls[idx] == q:\n",
    "                    min_ = q \n",
    "                else:\n",
    "                    min_ = ls[idx - 1] if idx - 1 >= 0 else -1\n",
    "            ans.append([min_, max_])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def closestNodes(self, root: Optional[TreeNode], queries: List[int]) -> List[List[int]]:\n",
    "        arr = []\n",
    "        \n",
    "        def dfs(node):\n",
    "            if node is not None:\n",
    "                dfs(node.left)\n",
    "                arr.append(node.val)\n",
    "                dfs(node.right)\n",
    "        \n",
    "        dfs(root)\n",
    "\n",
    "        ans_arr = []\n",
    "        for v in queries:\n",
    "            if v > arr[-1]:\n",
    "                ans_arr.append([arr[-1],-1])\n",
    "            elif v< arr[0]:\n",
    "                ans_arr.append([-1,arr[0]])\n",
    "            else:\n",
    "                i = bisect.bisect(arr,v)\n",
    "                if arr[i-1] == v:\n",
    "                    ans_arr.append([v,v])\n",
    "                else:\n",
    "                    ans_arr.append([arr[i-1],arr[i]])\n",
    "\n",
    "        return ans_arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def closestNodes(self, root: Optional[TreeNode], queries: List[int]) -> List[List[int]]:        \n",
    "        l = []\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return\n",
    "            dfs(node.left)\n",
    "            l.append(node.val)\n",
    "            dfs(node.right)\n",
    "            \n",
    "        \n",
    "        dfs(root)\n",
    "        print(l)\n",
    "        ans = []\n",
    "        len_ = len(l)\n",
    "        for n in queries:\n",
    "            i = bisect_left(l, n)\n",
    "            if i == len_:\n",
    "                max_ = -1\n",
    "            elif l[i] == n:\n",
    "                ans.append([n, n])\n",
    "                continue\n",
    "            elif n > l[-1]:\n",
    "                max_ = -1\n",
    "            else:\n",
    "                max_ = l[i]\n",
    "            min_ = l[i - 1]\n",
    "            if i == 0:\n",
    "                min_ = -1\n",
    "            ans.append([min_, max_])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def closestNodes(self, root: Optional[TreeNode], queries: List[int]) -> List[List[int]]:        \n",
    "        l = []\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return\n",
    "            dfs(node.left)\n",
    "            l.append(node.val)\n",
    "            dfs(node.right)\n",
    "        dfs(root)\n",
    "\n",
    "        def query(n):\n",
    "            if n > l[-1]:\n",
    "                return [l[-1], -1]\n",
    "            if n < l[0]:\n",
    "                return [-1, l[0]]\n",
    "            i = bisect_left(l, n)\n",
    "            return [n, n] if l[i] == n else [l[i - 1], l[i]]\n",
    "\n",
    "        return [*map(query, queries)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestNodes(self, root: Optional[TreeNode], queries: List[int]) -> List[List[int]]:\n",
    "        arr = []\n",
    "        def inorder(node):\n",
    "            if not node:\n",
    "                return\n",
    "            inorder(node.left)\n",
    "            arr.append(node.val)\n",
    "            inorder(node.right)\n",
    "        inorder(root)\n",
    "        res = []\n",
    "        for x in queries:\n",
    "            i = bisect.bisect_left(arr, x)\n",
    "            if i < len(arr) and arr[i] == x:\n",
    "                res.append([x, x])\n",
    "            else:\n",
    "                left = -1 if i== 0 else arr[i-1]\n",
    "                right = -1 if i == len(arr) else arr[i]\n",
    "                res.append([left, right])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def closestNodes(self, root: Optional[TreeNode], queries: List[int]) -> List[List[int]]:        \n",
    "        l = []\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return\n",
    "            dfs(node.left)\n",
    "            l.append(node.val)\n",
    "            dfs(node.right)\n",
    "        dfs(root)\n",
    "\n",
    "\n",
    "        def query(n):\n",
    "            if n > l[-1]:\n",
    "                return [l[-1], -1]\n",
    "            if n < l[0]:\n",
    "                return [-1, l[0]]\n",
    "\n",
    "            i = bisect_left(l, n)\n",
    "            if l[i] == n:\n",
    "                return [n, n]\n",
    "            max_ = l[i]\n",
    "            min_ = l[i - 1]\n",
    "            return [min_, max_]\n",
    "\n",
    "\n",
    "        return [*map(query, queries)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def closestNodes(self, root: Optional[TreeNode], queries: List[int]) -> List[List[int]]:\n",
    "        vals = []\n",
    "\n",
    "        def inorder(node):\n",
    "            if not node:\n",
    "                return\n",
    "            inorder(node.left)\n",
    "            # 添加节点值前检查是否已存在该值\n",
    "            if not vals or node.val > vals[-1]:\n",
    "                vals.append(node.val)\n",
    "            inorder(node.right)\n",
    "\n",
    "        # 执行中序遍历填充vals数组\n",
    "        inorder(root)\n",
    "\n",
    "        ans = []\n",
    "        for q in queries:\n",
    "            cur = [-1, -1]\n",
    "            idx = bisect.bisect_left(vals, q)\n",
    "            if idx != len(vals) and vals[idx] == q:\n",
    "                cur = [q, q]\n",
    "            else:\n",
    "                if idx != 0:\n",
    "                    cur[0] = vals[idx - 1]\n",
    "                if idx != len(vals):\n",
    "                    cur[1] = vals[idx]\n",
    "            ans.append(cur)\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def closestNodes(self, root: Optional[TreeNode], queries: List[int]) -> List[List[int]]:        \n",
    "        l = []\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return\n",
    "            dfs(node.left)\n",
    "            l.append(node.val)\n",
    "            dfs(node.right)\n",
    "            \n",
    "        \n",
    "        dfs(root)\n",
    "        print(l)\n",
    "        ans = []\n",
    "        len_ = len(l)\n",
    "        for n in queries:\n",
    "            i = bisect_left(l, n)\n",
    "            if i == len_:\n",
    "                max_ = -1\n",
    "            elif l[i] == n:\n",
    "                ans.append([n, n])\n",
    "                continue\n",
    "            elif n > l[-1]:\n",
    "                max_ = -1\n",
    "            else:\n",
    "                max_ = l[i]\n",
    "            \n",
    "            if i == 0:\n",
    "                min_ = -1\n",
    "            else:\n",
    "                min_ = l[i - 1]\n",
    "            ans.append([min_, max_])\n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
